package interview.Sorting;

public class QuickSort {
	private static int Partition(int[] num , int left, int right){
		if (left<=right){
			int mid = (left+right)/2;
			int i,j;
			i=left;
			j=right;
			int check = num[mid];
			while(i<j){
				while((num[i]<check))i++;
				while((num[j]>check))j--;
				
				if((i>j))break;
				Generic.swap(num, i, j);				
			}
			//Generic.swap(num,mid,i);
			return i;
		}
		return -1;
	}
	
	public static void sort(int[]num,int left, int right){
		int partition;
		if(left<=right){
			partition=Partition(num, left, right);			
			System.out.println("\n\nSort after the middle element " + num[partition] );
			Generic.printArray(num);
			sort(num,left,partition-1);
			sort(num,partition+1,right);
		}
	}
}
